package com.Offer;

/*
    面试题48：最长不含重复字符的子字符串
    从字符串中找到一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
    假设此字符串中只包含'a'~'z'的字符。
    例如在字符串：'arabcacfr'，最长的子字符串是'acfr'，长度为4
 */
public class demo48 {
    public static void main(String[] args) {
        String str = "arabcacfr";
        System.out.println(longestSubStringWithoutDuplication(str));
    }

    //创建长度为26的数组用于存储每一个字符上一次出现的位置，然后遍历每一个字符，如果没有出现或者出现在记录长度的字符串外部则长度+1
    //否则，记录现在的最长子字符串，并且从超出部分开始重新遍历后面的字符
    public static int longestSubStringWithoutDuplication(String str){
        if (str == null || str.length() <= 0){
            return 0;
        }
        int cur = 0;
        int max = 0;
        int[] position = new int[26];
        for (int i = 0; i < 26; i++) {
            position[i] = -1;
        }
        for (int i = 0; i < str.length(); i++) {
            int prevIndex = position[str.charAt(i)-'a'];
            if (prevIndex < 0 || i-prevIndex > cur){
                ++cur;
            }else{
                if(cur > max){
                    max = cur;
                }
                cur = i-prevIndex;
            }
            position[str.charAt(i)-'a'] = i;
        }
        if(cur > max){
            max = cur;
        }
        return max;
    }

}
